Bipartite Graph

定义 Definition

二分图 / 二部图：一种图（graph），其顶点集可以分成两个互不相交的部分 (U) 和 (V)，并且每条边都只连接 (U) 与 (V) 中的顶点（同一部分内的顶点之间没有边）。常用于表示“匹配/分配”关系（如人—任务、学生—课程）。
（也常简称为 bipartite；相关概念包括“二部匹配”等。）

发音 Pronunciation (IPA)

/baɪˈpɑːrtaɪt ɡræf/

例句 Examples

A bipartite graph has no edges between vertices in the same set.
二分图在同一组的顶点之间没有边相连。

We modeled the internship assignment problem as a bipartite graph and then used maximum matching to find an optimal pairing.
我们把实习分配问题建模为二分图，并用最大匹配来找到最优配对。

词源 Etymology

bipartite 来自拉丁语 *bi-*（“二、双”）+ partite（“分成部分的”，源自 part “部分”），字面意思是“分成两部分的”。在图论中与 graph（图） 结合，指“顶点可分为两部分且边只跨两部分连接”的图。

相关词 Related Words

• Bipartite
• Graph
• Vertex
• Edge
• Partition
• Matching
• Maximum Matching
• Complete Bipartite Graph
• Kőnig’s Theorem
• Hall’s Marriage Theorem

文学与著作 Literary Works

• Introduction to Graph Theory — Douglas B. West（教材中系统介绍二分图、匹配与相关定理）
• Graph Theory — Reinhard Diestel（经典图论教材，包含二分图的结构与判定，如与奇圈的关系）
• Combinatorial Optimization: Algorithms and Complexity — Christos H. Papadimitriou & Kenneth Steiglitz（以二分图匹配等为重要例子讨论优化与算法）
• The Probabilistic Method — Noga Alon & Joel H. Spencer（涉及二分图与随机方法在组合结构中的应用）